package 查找算法常用.二分查找10_14;

public class ArraysBinarySearch {

    // 有序二维数组如何实现二分查找
        // 假设matrix是一个m*n的有序二维数组，target是要查找的目标值
        public boolean searchMatrix(int[][] matrix, int target) {
            // 边界条件判断
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            // 获取二维数组的行数和列数
            int m = matrix.length;
            int n = matrix[0].length;
            // 将二维数组看作一个一维数组，其中每个元素是一个子数组
            // 定义一维数组的左右边界指针
            int left = 0;
            int right = m - 1;
            // 循环条件是左右指针不相交
            while (left <= right) {
                // 计算一维数组的中间位置，将其对应的子数组和目标值进行比较
                int mid = left + (right - left) / 2;
                int[] subArray = matrix[mid];
                // 如果目标值等于子数组的第一个或最后一个元素，则返回true
                if (target == subArray[0] || target == subArray[n - 1]) {
                    return true;
                }
                // 如果目标值小于子数组的第一个元素，则在一维数组的左半部分继续查找
                if (target < subArray[0]) {
                    right = mid - 1;
                }
                // 如果目标值大于子数组的最后一个元素，则在一维数组的右半部分继续查找
                else if (target > subArray[n - 1]) {
                    left = mid + 1;
                }
                // 如果目标值在子数组的第一个和最后一个元素之间，则在该子数组内进行普通的二分查找
                else {
                    return binarySearch(subArray, target);
                }
            }
            // 如果循环结束还没有找到目标值，则返回false
            return false;
        }

        // 普通的二分查找方法，用于在有序一维数组中查找目标值，返回布尔值表示是否存在
        public boolean binarySearch(int[] array, int target) {
            // 定义左右边界指针
            int left = 0;
            int right = array.length - 1;
            // 循环条件是左右指针不相交
            while (left <= right) {
                // 计算中间位置，将其对应的元素和目标值进行比较
                int mid = left + (right - left) / 2;
                int value = array[mid];
                // 如果目标值等于中间元素，则返回true
                if (target == value) {
                    return true;
                }
                // 如果目标值小于中间元素，则在左半部分继续查找
                if (target < value) {
                    right = mid - 1;
                }
                else {
                    left=mid+1;
                }
            }
            return false;
        }
}
